package com.example.demo.程序员面试金典;

import com.example.demo.leetcode100题.ListNode;

/**
 * @author：zzc
 * @date: 2022/9/7
 */
public class 分割链表 {

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {

        public ListNode partition(ListNode head, int x) {
            ListNode l1 = new ListNode(0);
            ListNode l2 = new ListNode(0);
            ListNode cur1 = l1, cur2 = l2;

            while (head != null) {
                if (head.val < x) {
                    cur1.next = head;
                    cur1 = cur1.next;
                }else {
                    cur2.next = head;
                    cur2 = cur2.next;
                }
                head = head.next;
            }
            cur1.next = l2.next;
            cur2.next = null;
            return l1.next;
        }
    }

}
